//堆排序(顺序存储)
/*
    堆是一棵"完全二叉树"(这里以首元素下标从1开始的数组为例)，结点i的左孩子是2i；右孩子是2i+1；父节点是i/2;编号 <=n/2 的结点都是分支结点
    大根堆(根 >= 左、右)；小根堆(根 <= 左、右)
*/
/*
算法思想(以大根堆为例)：建堆、排序
    建堆：编号 <=n/2 的所有结点从后往前依次"下坠"调整；调整规则：小元素逐层"下坠"(与关键字更大的孩子交换)
    排序：将堆顶元素加入有序子序列(堆顶元素与堆底元素交换)，堆底元素换到堆顶后，需要进行"下坠"调整，恢复"大根堆"的特性，重复n-1趟
*/
/*
    不稳定
    时间复杂度：建堆O(n)、排序O(nlogn)；故总的时间复杂度为O(nlogn);
    空间复杂度O(1);
*/

#include <iostream>

using namespace std;

//【"下坠"操作】将以第k个元素为根的子树调整为大根堆
void HeadAdjust(int A[], int k, int len)
{
    A[0] = A[k];                            //A[0]暂存子树的根节点(相当于temp)
    for (int i = 2 * k; i <= len; i *= 2)   //沿关键字较大的孩子结点不断向下筛选
    {
        if (i < len && A[i] < A[i+1])       //取关键字较大的孩子结点的下标
            i++;
        if (A[0] >= A[i])                   //筛选结束，退出循环(此时以第k个元素为根的子树本身就是一个大根堆)
            break;
        else
        {
            A[k] = A[i];                    //将A[i]上升到双亲结点上
            k = i;                          //修改k值，以便继续向下筛选
        }
    }
    A[k] = A[0];                            //被筛选结点的值放入最终位置
    return;
}

//建立大根堆
void BuildMaxHeap(int A[], int len)
{
    for (int i = len / 2; i > 0; --i) //从后往前调整所有非终端结点(数组从下标从1开始，则非终端节点为[1, ⌊len/2⌋]；若数组下标从0开始，则非终端节点为[0, ⌈len/2⌉])
        HeadAdjust(A, i, len);
    return;
}

//堆排序(这里是大根堆排序，即升序排序)
void HeapSort(int A[], int len) //len是大根堆(A[1……len])的长度；A[0]是暂存根节点的暂存单元，作用类似于temp。
{
    BuildMaxHeap(A, len);           //把完全二叉树初始化为大根堆
    for (int i = len; i > 1; --i)   //n-1趟的交换和重新建堆过程
    {
        swap(A[i], A[1]);           //堆顶元素和堆底元素
        HeadAdjust(A, 1, i - 1);    //把剩余的待排序元素整理成堆
    }
    return;
}


//测试代码
int main()
{
    int A[100] = {0, 2, 4, 3, 7, 9, 1, 6, 5, 8};
    HeapSort(A, 9);
    for (int i = 1; i < 10; ++i)
        cout << A[i] << ' ';
    return 0;
}